Search Results

Documents authored by Guinard, Brieuc


Document
Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths

Authors: Brieuc Guinard and Amos Korman

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
Search patterns of randomly oriented steps of different lengths have been observed on all scales of the biological world, ranging from microscopic to the ecological, including in protein motors, bacteria, T-cells, honeybees, marine predators, and more, see e.g., [Humphries et al., 2010; Jansen et al., 2012; Reynolds et al., 2017; Schuster and Levandowsky, 1996; Humphries et al., 2010; Viswanathan et al., 1996; Viswanathan et al., 1999]. Through different models, it has been demonstrated that adopting a variety in the magnitude of the step lengths can greatly improve the search efficiency. However, the precise connection between the search efficiency and the number of step lengths in the repertoire of the searcher has not been identified. Motivated by biological examples in one-dimensional terrains, a recent paper studied the best cover time on an n-node cycle that can be achieved by a random walk process that uses k step lengths [Boczkowski et al., 2018]. By tuning the lengths and corresponding probabilities the authors therein showed that the best cover time is roughly n^{1+Θ(1/k)}. While this bound is useful for large values of k, it is hardly informative for small k values, which are of interest in biology [Auger-Méthé et al., 2015; Bénichou et al., 2011; Lomholt et al., 2008; {Reynolds}, 2014]. In this paper, we provide a tight bound for the cover time of such a walk, for every integer k> 1. Specifically, up to lower order polylogarithmic factors, the cover time is n^{1+1/(2k-1)}. For k=2,3, 4 and 5 the bound is thus n^{4/3}, n^{6/5}, n^{8/7}, and n^{10/9}, respectively. Informally, our result implies that, as long as the number of step lengths k is not too large, incorporating an additional step length to the repertoire of the process enables to improve the cover time by a polynomial factor, but the extent of the improvement gradually decreases with k.

Cite as

Brieuc Guinard and Amos Korman. Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{guinard_et_al:LIPIcs.STACS.2020.28,
  author =	{Guinard, Brieuc and Korman, Amos},
  title =	{{Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.28},
  URN =		{urn:nbn:de:0030-drops-118892},
  doi =		{10.4230/LIPIcs.STACS.2020.28},
  annote =	{Keywords: Computational Biology, Randomness in Computing, Search Algorithms, Random Walks, L\'{e}vy Flights, Intermittent Search, CCRW}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail